This invention relates to the field of network analysis, and in particular to a method and system that receives a set of individual network topologies and forms a composite network topology by determining the connections between the individual network topologies.
A common task in the field of network analysis is to determine the topology of the network that is to be analyzed. If the network is small, a human may create a computer-readable topological model of the network, and provide that model to network analysis tools that require such a model.
If the network is larger, a computer program may be configured to query the devices in the network for information that can be used to deduce or infer the interconnections among these devices. For example, the configuration of the routers in the network, including the current routing table and interface information for each router, may be used to determine the paths that messages will take as they propagate from one device to another device via such routers. In like manner, the configuration information at other devices may be used to further determine the connections among the devices. Some of the data used to infer connectivity include, for example:
IP addressing data, which provides Layer 3 view of the network.
Neighbor discovery data, which provides information about neighbors that are connected to a device, and hence assists in inferring a Layer 2 topology. Example products include Cisco Discovery Protocol, and Link Layer Discovery Protocol.
Forwarding table data, which contains the physical addresses of interfaces that are reachable through another interface. This data may be used in Layer 2 topology inference, although the data is often incomplete and volatile.
BGP neighbor data, which provides border connectivity information with different Autonomous Systems (AS).
Logical tunnel and virtual circuit definitions, which provides logical connectivity data.
Unfortunately, the time required to assess the configuration of each device to determine a possible connection to each of the other devices in the network increases exponentially as the size of the network increases. At some point, the time required to determine the topology of a very large network makes such a determination infeasible, or at least impractical for use in any real-time or near-time analyses, such as analyses used to detect and correct problems within the network.
It would be advantageous to provide a method and system that is able to determine, or estimate, the topology of a very large network without incurring an exponential increase in time for larger and larger networks. It would also be advantageous to provide a method and system that distributes the process of topology determination among a variety of processors, allowing for substantial parallel processing.
These advantages, and others, can be realized by a method and system that takes advantage of processes that are efficient for determining the topology of small to medium size networks to determine individual network topologies for such networks, and then merges these individual topologies into a consolidated topology for the entire network. Each of the processes that determine the topology of the smaller networks provides the determined network topology, as well as a list of factors that may be relevant in the determination of how the given topology might be attached to any other given topology, such as the identification of a node that is not included in the given topology, or other indications of external connections. The merging process is configured to substantially restrict its analysis to these factors, thereby limiting the extent, and therefore the time consumed, by this merging process.
Network topology inference algorithms use large amounts of data collected from network devices. Modern networks are very large with tens of thousands of network devices in them. Management or topology inference on such networks is not very scalable for networks of this size. A typical approach is to logically spread the devices across different management systems, with each system maintaining its associated topology. Such a setup, however, fails to give a consolidated and complete network topology to a network administrator. Hence, network management systems fall short of achieving their full potential in terms of convenience to network administrators.
This invention overcomes this issue by providing a comprehensive network view of a network by stitching topologies based on varying levels of relationships between network devices that are managed by different network management systems.
Throughout the drawings, the same reference numerals indicate similar or corresponding features or functions. The drawings are included for illustrative purposes and are not intended to limit the scope of the invention.